/*
 * Copyright (c) 2018-2022, 四川蜀天梦图数据科技有限公司.
 * All rights reserved.
 */

package tree

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/ leetcode-105
func buildTree(preorder []int, inorder []int) *TreeNode {
	root := &TreeNode{Val: preorder[0]}
	if len(preorder) == 1 {
		return root
	}
	var rootIndex int
	for i, v := range inorder {
		if v == root.Val {
			rootIndex = i
			break
		}
	}

	var leftTreeLen, rightTreeLen int
	leftTreeLen = len(inorder[:rootIndex])
	if rootIndex+1 < len(inorder) {
		rightTreeLen = len(inorder[rootIndex+1:])
	}
	if leftTreeLen > 0 {
		root.Left = buildTree(preorder[1:leftTreeLen+1], inorder[:rootIndex])
	}

	if rightTreeLen > 0 {
		root.Right = buildTree(preorder[leftTreeLen+1:], inorder[rootIndex+1:])
	}

	return root
}

// https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/ leetcode-106
func buildTree0(inorder []int, postorder []int) *TreeNode {
	if len(inorder) == 0 {
		return nil
	}

	root := &TreeNode{Val: postorder[len(postorder)-1]}
	if len(inorder) == 1 {
		return root
	}

	var rootIndex int
	for i, v := range inorder {
		if v == root.Val {
			rootIndex = i
			break
		}
	}
	var leftTreeLen, rightTreeLen int
	leftTreeLen = len(inorder[:rootIndex])
	if rootIndex+1 < len(inorder) {
		rightTreeLen = len(inorder[rootIndex+1:])
	}

	if leftTreeLen > 0 {
		root.Left = buildTree0(inorder[:rootIndex], postorder[:leftTreeLen])
	}

	if rightTreeLen > 0 {
		root.Right = buildTree0(inorder[rootIndex+1:], postorder[leftTreeLen:len(postorder)-1])
	}
	return root
}
